package com.dhu.graph.digraph;

import com.dhu.graph.basic.GraphImpls.DiGraph;

/**
 * @ Author ：snow
 * @ Date   ：Created in 2020-05-03
 * @ Description：有向图的深度优先搜索，有向图的可达性问题，回答是否存在一条从指定的点s到顶点v的有向路径
 * @ Modified By：
 * @ Version:
 */
public class DirectedDFS {

    private boolean[] marked;      //

    /**
     * 是否存在由起点s 指向有向图中任一顶点v的有向路径
     * @param G
     * @param s
     */
    public DirectedDFS(DiGraph G, int s){
        this.marked = new boolean[G.V()];
        dfs(G, s);
    }
    public DirectedDFS(DiGraph G, Iterable<Integer> bag){
        this.marked = new boolean[G.V()];
        for (Integer w : bag) {
            dfs(G, w);
        }
    }

    private void dfs(DiGraph G, int s){
        marked[s] = true;
        for (Integer v : G.adj(s)) {
            if (!marked[v]){
                dfs(G, v);
            }
        }
    }

    // 顶点v 是否可达
    public boolean marked(int v){
        return marked[v];
    }
}
